package leecode

func numDecodings(s string) int {

	dp := make([]int, len(s)) //dp数组为到第i位的解码方法有几种
	//初始化dp
	if s[:1] > "0" {
		dp[0] = 1
	} else {
		return 0
	}
	if len(s) <= 1 {
		return 1
	}
	if s[1] != '0' {
		dp[1] = dp[0]
		if s[:2] >= "10" && s[:2] <= "26" {
			dp[1]++
		}
	} else {
		if s[:2] >= "10" && s[:2] <= "26" {
			dp[1] = 1
		} else {
			dp[1] = 0
		}
	}
	for i := 2; i < len(s); i++ {
		if s[i] != '0' {
			dp[i] += dp[i-1]
		}
		if s[i-1:i+1] >= "10" && s[i-1:i+1] <= "26" {
			dp[i] += dp[i-2]
		}
	}

	return dp[len(dp)-1]
}
